package LeetCode热题HOT100;

import 剑指offer.ListNode;

public class p148排序链表 {
    public ListNode sortList(ListNode head) {
        //基于递归的 归并排序
        if (head==null||head.next==null) {
            // 头结点为空直接返回，
            // 或者
            // 遍历到1个结点时，直接返回
            return head;
        }

        //利用快慢指针找到中间位置
        ListNode fast=head.next;
        ListNode slow=head;
        while (fast!=null && fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
        }

        ListNode head2=slow.next;
        slow.next=null;
        ListNode left=sortList(head);//返回排好序前一半的头结点
        ListNode right=sortList(head2);//返回排好序后一半的头结点

        ListNode p=new ListNode(0);//傀儡节点
        ListNode res=p;
        while (left!=null && right!=null) {
            if (left.val<right.val) {
                p.next=left;
                left=left.next;
            }else {
                p.next=right;
                right=right.next;
            }
            p=p.next;
        }

        p.next=(left!=null)?left:right;
        return res.next;

    }
}
